﻿using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using C5;

namespace GISCore.Geometry.Intersectors
{   
    public class SweepLineII : IIntersector
    {
        public static double sweepPoint = 0.0;
        public bool ifDebug=true;
        //A tree set is an ordered set with unique elements
        public TreeSet<IntersectPoint> IntersectPointSets= new TreeSet<IntersectPoint>(new IntersectPointComparator());
        public SweepLineII() { }

        public IEnumerable<IntersectPoint> Intersect(IEnumerable<Line> lines)
        {
            Debug.Assert(lines != null);
            return Sweep(lines);
        }

        /// <summary>
        /// This class is used for the comparator of treeset data structure which stores intersect points;
        /// A intersect point is considered identical to another line only when its inbound line and outbound line are the same
        /// as another line's.
        /// </summary>
        private class IntersectPointComparator : IComparer<IntersectPoint>
        {
            public int Compare(IntersectPoint x, IntersectPoint y)
            {
                int value=1;
                if ((x.inComingLine == y.inComingLine) && (x.outGoingLine == y.outGoingLine))
                {
                    value = 0;
                }
                return value;
            }
        }

        /// <summary>
        /// append a intersect point to the set of intersect points.
        /// </summary>
        /// <param name="inter"></param>
        /// <param name="left"></param> inbound line.
        /// <param name="right"></param> outbound line.
        /// <returns></returns> if this intersect point is successfullly added to the intersect point set.
        private bool _addIntersection(IntersectPoint inter, Line left, Line right)
        {
            inter.inComingLine = left;
            inter.outGoingLine = right;
            return IntersectPointSets.Add(inter);
        }

        /// <summary>
        /// Runs a sweep line along a list of line segments to determine intersection points
        /// </summary>
        /// <param name="lines">the list of line segments</param>
        /// <returns>the intersection points</returns>
        private List<IntersectPoint> Sweep(IEnumerable<Line> lines)
        {
            Debug.Assert(lines != null);
            //var intersections = new System.Collections.Generic.HashSet<IntersectPoint>();
            EventQueue eventQueue = new EventQueue(lines);
            StatusTree statusTree = new StatusTree();            
             //Console.WriteLine("evenPair" + eventPair.ToString());
            if (ifDebug)
            {
                Console.WriteLine("*******************Start***********************");
                Console.WriteLine("eventQueue");
                foreach (var de in eventQueue.getTree().ToList())
                {

                    Console.Write(" key: " + de.Key.ToString() + " value: " + de.Value.Count + "|");
                }
                Console.WriteLine("");
                Console.WriteLine("******************************************");
            }
            while (!eventQueue.IsEmpty)
            {
                //implement the algorithm described in http://www.softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm#Bentley-Ottmann%20Algorithm
                // The algorithm is as follows:
                // 1. Initially, the starting point and ending point of each of the line segments is pushed into eventQueue.
                // 2. Then iteratively pop a point and its related lines out of the eventQueue and do the following until the eventQueue becomes empty.
                //      2.1 if a point is the point above the other point in the line, then add the line into the StatusTree, and test if this line 
                //          intersects with its left or right neighbour in the StatusTree.
                //      2.2 if a point is the point below the other point in the line, then remove the line from the StatusTree, and test if this line
                //          intersects with its left or right neighbour in the StatusTree.
                //      2.3 if a point is a intersect point, try to add that point to the intersect point set.
                Line left = null;
                Line right = null;
                IntersectPoint inter = null;
                var eventPair = eventQueue.DeleteMin();
                if (ifDebug)
                {
                    Console.WriteLine("evenPair: " + eventPair.EventPoint);
                }
                foreach (var l in eventPair.EventLines)
                {
                    sweepPoint = eventPair.EventPoint.getY();
                    // if this is an intersect point
                    if (l.flag == 3)
                    {
                        //left = eventPair.EventLines[0].l;
                        //right = eventPair.EventLines[1].l;
                        //statusTree.remove(left);
                        //statusTree.remove(right);
                        //statusTree.Insert(left);
                        //statusTree.Insert(right);
                        if (ifDebug)
                        {
                            Console.WriteLine("deleting " + l.l.ToString());
                        }
                        if (statusTree.remove(l.l))
                        {
                            if (ifDebug)
                            {
                                Console.WriteLine("inserting " + l.l.ToString());
                            }
                                statusTree.Insert(l.l);
                        }
                        else
                        {
                            if (ifDebug)
                            {
                                Console.WriteLine("cancel deleting " + l.l.ToString());
                            }
                        }
                        
                        //statusTree.GetNeighbors(l.l, out left, out right);
                        //Console.Write(" type 3: line: " + l.l.ToString());
                        //Console.Write(" left: " + left);
                        //Console.WriteLine(" right: " + right);
                        //if ((left != null) && (right != null))
                        //{
                        //    _findNewEvent(left, right, eventPair.EventPoint, eventQueue, out inter);
                        //    if (inter != null)
                        //    {
                        //        Console.WriteLine("ending an point" + inter);
                        //    }

                        //}
                        if (ifDebug)
                        {
                            Console.WriteLine("intersect point " + eventPair.EventPoint.ToString());
                        }
                        statusTree.GetNeighbors(l.l, out left, out right);
                        if (ifDebug)
                        {
                            Console.Write("type 3: line: " + l.l.ToString());
                            Console.Write(" left: " + left);
                            Console.WriteLine(" right: " + right);
                        }
                        if (left != null)
                        {
                            _findNewEvent(left, l.l, eventPair.EventPoint, eventQueue, out inter);
                            if (inter != null)
                            {
                                if (ifDebug)
                                {
                                    Console.WriteLine("adding a new point" + inter);
                                }
                            }

                        }
                        if (right != null)
                        {
                            _findNewEvent(l.l, right, eventPair.EventPoint, eventQueue, out inter);
                            if (inter != null)
                            {
                                if (ifDebug)
                                {
                                    Console.WriteLine("adding a new point" + inter);
                                }
                             }

                        }
                        //statusTree.Insert(l.l); 
                    }
                    // if this is an lower point
                    else if (l.flag== 2)
                    {
                        statusTree.GetNeighbors(l.l, out left, out right);
                        if (ifDebug)
                        {
                            Console.Write(" type 2: line: " + l.l.ToString());
                            Console.Write(" left: " + left);
                            Console.WriteLine(" right: " + right);
                        }
                        if ((left != null)&&(right!=null))
                        {
                            _findNewEvent(left, right, eventPair.EventPoint, eventQueue, out inter);
                            if (inter != null)
                            {
                                if (ifDebug)
                                {
                                    Console.WriteLine("ending an point" + inter);
                                }
                            }

                        }
                        statusTree.remove(l.l);
                    }
                    // if this is an upper point
                    else
                    {
                       
                        statusTree.GetNeighbors(l.l, out left, out right);
                        if (ifDebug)
                        {
                            Console.Write("type 1: line: " + l.l.ToString());
                            Console.Write(" left: " + left);
                            Console.WriteLine(" right: " + right);
                        }
                        if (left != null)
                        {
                            _findNewEvent(left, l.l, eventPair.EventPoint, eventQueue, out inter);
                            if (inter != null)
                            {
                                if (ifDebug)
                                {
                                    Console.WriteLine("adding a new point" + inter);
                                }
                            }
                            
                        }
                        if (right != null)
                        {
                            _findNewEvent(l.l, right, eventPair.EventPoint, eventQueue, out inter);
                            if (inter != null)
                            {
                                if (ifDebug)
                                {
                                    Console.WriteLine("adding a new point" + inter);
                                }
                            }
                            
                        }
                        statusTree.Insert(l.l); 
               
                    }
                }
                //var ps = _handleEventPoint(eventPair, eventQueue, statusTree);
                //ps.ForEach((p) => intersections.Add(p));
                if (ifDebug)
                {
                    Console.WriteLine("eventQueue");
                    foreach (var de in eventQueue.getTree().ToList())
                    {

                        //Console.Write(" key: " + de.Key.ToString()+" value: "+de.Value.Count+"|");
                    }
                    Console.WriteLine("");
                    Console.WriteLine("statusTree");
                    foreach (var de in statusTree.getTree().ToList())
                    {

                        Console.Write(de.ToString() + "|");
                    }
                    Console.WriteLine("intersection" + IntersectPointSets.Count);
                    Console.WriteLine("******************************************");
                }
            }
            for (int i = 0; i < IntersectPointSets.Count; i++)
            {
                Console.WriteLine("The " + i + "th intersect point is " + IntersectPointSets[i].ToString());
            }
            return IntersectPointSets.ToList();
        }


        /// <summary>
        /// Finding the intersect point and add that intersect point to the eventQueue.
        /// </summary>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <param name="eventPoint"></param>
        /// <param name="eventQueue"></param>
        /// <param name="inter"></param>
        /// <returns></returns>
        private bool _findNewEvent(Line left, Line right, Point eventPoint, EventQueue eventQueue, out IntersectPoint inter)
        {
            bool inserted = false;
            inter = null;
            if (left != null && right != null)
            {
                if (left.getPolygon() == right.getPolygon())
                {
                    inter = null;
                    return false;
                }
                //calculate the intersect points
                if (left.getIntersect(right, out inter) == Intersection.True)
                {
                    // these are properties of the total ordering that must hold for this
                    // to be a valid intersection
                    if (inter.Y < eventPoint.Y || (inter.Y == eventPoint.Y && inter.X > eventPoint.X))
                    {
                        if (_addIntersection(inter, left, right))
                        {
                            //add the intersect point to the eventQueue.
                            eventQueue.Add(inter, new LineEntry(left, 3));
                            eventQueue.Add(inter, new LineEntry(right, 3));
                            inserted = true;
                        }
                        else
                        {
                            inter = null;
                            inserted = false;
                        }
                    }
                    //it is possible that the intersect point is right at the sweep line point.
                    else if ((inter.Y == eventPoint.Y) && (inter.X == eventPoint.X))
                    {

                    }
                    else
                    {
                        inter = null;
                    }
                }
                                
            }
            return inserted;
        }

        /// <summary>
        /// The EventQueue will maintain the order of events to handle.
        /// The order on event points is defined as the following:
        ///     Given points p and q, p < q IFF
        ///         p_y > q_y holds OR
        ///         p_y == q_y and p_x < q_x
        /// </summary>
        private class EventQueue
        {
            // Each point is associated with a set of LineEntry objects.
            private TreeDictionary<Point, List<LineEntry>> _eq;

            public TreeDictionary<Point, List<LineEntry>> getTree()
            {
                return _eq;
            }

            public EventQueue(IEnumerable<Line> lines)
            {
                Debug.Assert(lines != null);

                _eq = new TreeDictionary<Point, List<LineEntry>>(new EventPointComparer());
                var epc = new EventPointComparer();

                // as we add the point/line pairs only add the lines
                // to the upper points. leftmost point is for tiebreaking
                foreach (var line in lines)
                {
                    // for lines parallel to y coordinate
                    if (line.getACoefficient() == 0)
                    {
                        
                        int result1 = epc.Compare(line.Start, line.End);
                        if(result1==1){
                            this.Add(line.End,new LineEntry(line,4));
                        }
                        else if(result1==-1){
                            this.Add(line.Start,new LineEntry(line,4));
                        }
                     continue;
                    }
                    int result = epc.Compare(line.Start, line.End);
                    switch (result)
                    {
                        //start point is above end point
                        case -1:
                            this.Add(line.Start, new LineEntry(line,1));
                            this.Add(line.End, new LineEntry(line, 2));
                            break;
                        case 0:
                        //start point is below end point    
                        case 1:
                            this.Add(line.Start, new LineEntry(line,2));
                            this.Add(line.End, new LineEntry(line, 1));
                            break;
                    }
                    //this.Add(StartEntry,line);
                    //this.Add(EndEntry,line);
                }
                
            }

            public bool Add(Point p, LineEntry line)
            {
                Debug.Assert(p != null);
                bool inserted = false;

                if (!_eq.Contains(p))
                {
                    _eq.Add(p, new List<LineEntry>());
                    //_eq[p].Add(line);
                    inserted = true;
                }
                if (line != null)
                {
                    _eq[p].Add(line);
                }
                return inserted;
            }

            public EventPair DeleteMin()
            {
                Debug.Assert(!_eq.IsEmpty);

                var t = _eq.DeleteMin();
                return new EventPair(t.Key, t.Value);
            }

            public bool IsEmpty { get { return _eq.IsEmpty; } }

            public override string ToString()
            {
                return _eq.ToString();
            }

            /// <summary>
            /// The order on event points is defined as the following:
            ///     Given points p and q, p < q IFF
            ///         p_y > q_y holds OR
            ///         p_y == q_y and p_x < q_x
            /// </summary>
            private class EventPointComparer : IComparer<Point>
            {
                public int Compare(Point a, Point b)
                {
                    int val = 0;
                    if (a.Y > b.Y)
                    {
                        val = -1;
                    }
                    else if (a.Y < b.Y)
                    {
                        val = 1;
                    }
                    else
                    {
                        if (a.X < b.X)
                        {
                            val = -1;
                        }
                        else if (a.X > b.X)
                        {
                            val = 1;
                        }
                        else
                        {
                            val = 0;
                        }
                    }
                    return val;
                }
            }

            public class EventPair
            {
                public Point EventPoint { get; private set; }
                public List<LineEntry> EventLines { get; private set; }
                public EventPair(Point p, List<LineEntry> lines)
                {
                    EventPoint = p;
                    EventLines = lines;
                }
                public override string ToString()
                {
                    return string.Format("{0} => {1}", EventPoint, EventLines);
                }
            }
           
        }
        public class LineEntry
            {
                public Line l { get; set; }
                public int flag { get; set; }
                //flag=1 start point flag=2 end point
                public LineEntry(Line l, int flag)
                {
                    this.l = l;
                    this.flag = flag;
                }
            }
        /// <summary>
        /// The StatusTree will maintain the state of the algorithm. It is a left to right ordering of the points.
        /// </summary>
        private class StatusTree
        {
            private TreeSet<Line> _tree;

            public TreeSet<Line> getTree()
            {
                return _tree;
            }

            public StatusTree()
            {
                _tree = new TreeSet<Line>(new StatusLineComparer());
            }

           
            /// <summary>
            /// this will add a line with the associated eventpoint
            /// </summary>
            /// <param name="line">the line to add</param>
            /// <returns>if the line was inserted</returns>
            public bool Insert(Line line)
            {
                Debug.Assert(line != null);
                return _tree.Add(line);
            }

            /// <summary>
            /// this will get the immediate left and right neighbor lines of the eventpoint
            /// </summary>
            /// <param name="eventPoint"></param>
            /// <param name="left"></param>
            /// <param name="right"></param>
            public void GetNeighbors(Point eventPoint, out Line left, out Line right)
            {
                Debug.Assert(eventPoint != null);
                //this is a trick to make a line, that really is just a point
                Line tmp = new Line(eventPoint, eventPoint);
                GetNeighbors(tmp, out left, out right);
            }

            public void GetNeighbors(Line line, out Line left, out Line right)
            {
                Debug.Assert(line != null);
                if (!_tree.TryPredecessor(line, out left))
                {
                    if (!_tree.TryWeakPredecessor(line, out left))
                    {
                        left = null;
                    } 
                }
                if (!_tree.TrySuccessor(line, out right))
                {
                    if (!_tree.TryWeakSuccessor(line, out right))
                    {
                        right = null;
                    }
                }
            }

            public override string ToString()
            {
                return _tree.ToString();
            }

            public bool remove(Line l)
            {
                bool ret = false;
                ret = _tree.Remove(l);
                if (!ret)
                {
                    //if (ifDebug)
                    //{
                    //    Console.WriteLine("fail to delete " + l.ToString());
                    //}
                }
                return ret;
            }

            private class StatusPointComparer : IComparer<Point>
            {
                public int Compare(Point x, Point y)
                {
                    return (x.X < y.X) ? -1 : (x.X == y.X) ? 0 : 1;
                }
            }
            /// <summary>
            /// Comparer class for two lines
            /// Given lines n,m:
            ///     n < m iff:
            ///         n.Left < m.Left OR
            ///         n.Left = m.Left, n.Right < m.Right
            /// </summary>
            private class StatusLineComparer : IComparer<Line>
            {
                public int Compare(Line x, Line y)
                {
                    int value;
                    var spc = new StatusPointComparer();
                    double tempx=x.getSweepPoint(sweepPoint);
                    double tempy=y.getSweepPoint(sweepPoint);
                    Point pointX;
                    Point pointY;
 
                    if ((tempx-tempy) > Constants.ZERO)
                    {
                        value = 1;
                    }
                    else if ((tempx - tempy) < Constants.NZERO )
                    {
                        value = -1;
                    }
                    else
                    {

                        if (x.Start.getY() > x.End.getY())
                        {
                            pointX = x.End;
                        }
                        else
                        {
                            pointX = x.Start;
                        }
                        if (y.Start.getY() > y.End.getY())
                        {
                            pointY = y.End;
                        }
                        else
                        {
                            pointY = y.Start;
                        }
                        if (pointX.getX() > pointY.getX())
                        {
                            value = 1;
                        }
                        else if (pointX.getX() < pointY.getX())
                        {
                            value = -1;
                        }
                        else value = 0;
                        if ((sweepPoint > 8.3) && (sweepPoint < 8.4))
                        {
                            //Console.WriteLine("******************start******************");
                            //Console.WriteLine("x;" + pointX.ToString());
                            //Console.WriteLine("y;" + pointY.ToString());
                        }

                    }
                    if ((sweepPoint >8.3) && (sweepPoint<8.4))
                    {
                        //Console.WriteLine(x.ToString() + ";" + y.ToString());
                        //Console.WriteLine("tempx= " + tempx + " tempy= " + tempy + " value= " + value);
                        //Console.WriteLine("******************end******************");
                    }
                    return value;
                }
            }

        }
    }
}
